<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      /**
       * 先排序，再循环，把结果集里的最后一个和数组里比较是否重叠，重叠则进结果集
       * 优化点：
       * 1.不要又出有入
       * @param {number[][]} intervals
       * @return {number[][]}
       */
      /**
       * 合并区间数组。将给定的区间数组进行合并，返回一个新的区间数组，其中所有重叠的区间被合并成一个。
       * @param {Array<Array<number>>} intervals - 一个包含区间的数组，每个区间由两个数字组成，表示起始和结束位置。
       * @return {Array<Array<number>>} 返回合并后的区间数组。
       */
      var merge = function (intervals) {
        // 如果区间数组为空，则直接返回空数组
        if (intervals.length < 1) return [];
        // 按区间的起始位置对数组进行升序排序
        intervals.sort((a, b) => a[0] - b[0]);
        // 初始化结果数组，将排序后的第一个区间加入其中
        const res = [intervals[0]];
        // 遍历排序后的区间数组，从第二个区间开始处理
        for (let index = 1; index < intervals.length; index++) {
          // 获取当前结果数组中的最后一个区间和当前遍历到的区间
          const cur = res[res.length - 1];
          const next = intervals[index];
          // 判断当前区间和结果数组中的最后一个区间是否重叠
          if (isRangeMatch(cur, next)) {
            // 如果重叠，则将两个区间合并，并更新结果数组中的最后一个区间
            res[res.length - 1] = [
              Math.min(cur[0], next[0]), // 合并区间的起始位置为两个区间起始位置的较小值
              Math.max(cur[1], next[1]), // 合并区间的结束位置为两个区间结束位置的较大值
            ];
          } else {
            // 如果不重叠，则将当前区间直接加入结果数组
            res.push(next);
          }
        }
        console.log(res);
        return res;
      };

      /**
       * 先排序，再循环，把结果集里的最后一个和数组里比较是否重叠，重叠则进结果集
       *
       * @param {number[][]} intervals
       * @return {number[][]}
       */
      var merge = function (intervals) {
        if (intervals.length < 1) return [];
        intervals.sort((a, b) => a[0] - b[0]);
        const res = [intervals[0]];
        for (let index = 1; index < intervals.length; index++) {
          const cur = res.pop();
          const next = intervals[index];
          if (isRangeMatch(cur, next)) {
            res.push([Math.min(cur[0], next[0]), Math.max(cur[1], next[1])]);
          } else {
            res.push(cur, next);
          }
        }
        console.log(res);
        return res;
      };

      function isRangeMatch(range1, range2) {
        const [a1, b1] = range1;
        const [a2, b2] = range2;
        return !(b1 < a2 || b2 < a1);
      }

      merge([
        [2, 3],
        [4, 5],
        [6, 7],
        [8, 9],
        [1, 10],
      ]);
      [[1, 10]];
    </script>

    <script>
      //效率为1ms毫秒的

      //         class Solution {
      //     /**
      //      * 合并区间。
      //      * 给定一个区间数组，表示多个不重叠或可能重叠的区间，
      //      * 目标是合并所有重叠区间，返回一个新的区间数组，其中所有区间互不重叠且完全覆盖输入区间。
      //      *
      //      * @param intervals 区间数组，每个区间由两个整数表示，如 intervals[i] = [starti, endi]。
      //      * @return 合并后的不重叠区间数组。
      //      */
      //     public int[][] merge(int[][] intervals) {
      //         // 初始化最大值和最小值，用于确定整个输入区间范围
      //         int max = Integer.MIN_VALUE;
      //         int min = Integer.MAX_VALUE;

      //         // 遍历所有区间，找到整个输入区间的最大值和最小值
      //         for (int[] interval : intervals) {
      //             max = Math.max(interval[1], max);
      //             min = Math.min(interval[0], min);
      //         }

      //         // 使用数组array来记录每个位置的最大结束值，以处理重叠区间
      //         int[] array = new int[max - min + 1];
      //         // 初始化数组array
      //         Arrays.fill(array, -1);
      //         // 遍历所有区间，更新数组array
      //         for (int[] interval : intervals) {
      //             // 将区间起点转换为相对于整个输入区间范围的索引值
      //             int left = interval[0] - min;
      //             // 更新数组 array 中对应索引位置的值，确保它始终存储着该位置上区间结束的最大值
      //             array[left] = Math.max(array[left], interval[1]);
      //         }

      //         // 使用链表result来存储合并后的区间
      //         LinkedList<int[]> result = new LinkedList<>();
      //         for (int i = 0; i < array.length; i++) {
      //             if (array[i] == -1) {
      //                 continue;
      //             }
      //             int left = i + min;
      //             int right = array[i];

      //             // 如果链表为空或当前区间与前一区间不重叠，则直接添加
      //             if (result.size() == 0 || left > result.getLast()[1]) {
      //                 result.add(new int[]{left, right});
      //             } else {
      //                 // 如果当前区间与前一区间重叠，则更新前一区间的右边界
      //                 if (result.getLast()[1] < right) {
      //                     result.getLast()[1] = right;
      //                 }
      //             }
      //         }
      //         // 将链表转换为数组并返回
      //         return result.toArray(new int[][]{});
      //     }
      // }

      class Solution {
        /**
         * 合并区间。
         * 给定一个区间数组，表示多个不重叠或可能重叠的区间，
         * 目标是合并所有重叠区间，返回一个新的区间数组，其中所有区间互不重叠且完全覆盖输入区间。
         *
         * @param intervals 区间数组，每个区间由两个整数表示，如 intervals[i] = [starti, endi]。
         * @return 合并后的不重叠区间数组。
         */
        merge(intervals) {
          // 初始化最大值和最小值，用于确定整个输入区间范围
          let max = Integer.MIN_VALUE;
          let min = Integer.MAX_VALUE;

          // 遍历所有区间，找到整个输入区间的最大值和最小值
          for (const interval of intervals) {
            max = Math.max(interval[1], max);
            min = Math.min(interval[0], min);
          }

          // 使用数组array来记录每个位置的最大结束值，以处理重叠区间
          const array = new Array(max - min + 1).fill(-1);
          // 初始化数组array
          Arrays.fill(array, -1);
          // 遍历所有区间，更新数组array
          for (const interval of intervals) {
            // 将区间起点转换为相对于整个输入区间范围的索引值
            const left = interval[0] - min;
            // 更新数组 array 中对应索引位置的值，确保它始终存储着该位置上区间结束的最大值
            array[left] = Math.max(array[left], interval[1]);
          }

          // 使用链表result来存储合并后的区间
          const result = [];
          for (let i = 0; i < array.length; i++) {
            if (array[i] === -1) {
              continue;
            }
            const left = i + min;
            const right = array[i];

            // 如果链表为空或当前区间与前一区间不重叠，则直接添加
            if (result.length === 0 || left > result[result.length - 1][1]) {
              result.push([left, right]);
            } else {
              // 如果当前区间与前一区间重叠，则更新前一区间的右边界
              if (result[result.length - 1][1] < right) {
                result[result.length - 1][1] = right;
              }
            }
          }
          // 将链表转换为数组并返回
          return result;
        }
      }
    </script>
  </body>
</html>
